package main

import (
	"fmt"
	"math/rand"
	"time"
)

func test() {
	//22
	var arr1 [80000]int
	for i := 0; i < len(arr1); i++ {
		arr1[i] = rand.Intn(len(arr1))
	}
	// arr1 := [...]int{6, 1, 2, 7, 9, 3, 4, 5, 10, 8}
	agoTime := time.Now().Unix()
	QuickSort(arr1[:], 0, len(arr1)-1)
	afterTime := time.Now().Unix()
	fmt.Println("排序总共用了", afterTime-agoTime, "秒")

}

// 冒泡排序
func BubbleSort(arr []int) (result []int) {
	len := len(arr)
	changed := false //没有需要交换的则说明数组已经排好序了
	for i := 0; i < len-1; i++ {
		for j := 0; j < len-1-i; j++ {
			if arr[j] < arr[j+1] {
				changed = true
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
		if !changed { //已经排好序不用循环了
			break
		}
	}
	return arr
}

// 快速排序
func QuickSort(arr []int, left, right int) {

	l := left                    //左下标
	r := right                   //右下标
	pivot := arr[(left+right)/2] //pivot 作为中轴

	for l < r { //循环的目的是让比pivot值小的放到左边比pivot值大的放右边

		for arr[l] < pivot { //在pivot的左边一直找到大于等于pivot的值才退出
			l += 1
		}


		for arr[r] > pivot { //在pivot的右边一直找到小于等于pivot的值才退出
			r -= 1
		}

		if l >= r { //如果l>=r说明pivot的左右两边已经按照左边全是小于等于pivot的值，右边全是大于等于pivot的值
			break
		}

		//交换
		arr[l], arr[r] = arr[r], arr[l]

		if arr[l] == pivot { //如果交换后发现这个arr[l]==pivot,r--, 前移;
			r -= 1
		}

		if arr[r] == pivot { //后移
			l += 1
		}

	}
	//如果l==r,必须l++，r-- 否则会出现栈溢出
	if l == r {
		l += 1
		r -= 1
	}

	if left < r { //向左递归
		QuickSort(arr, left, r)
	}

	if right > l { //向右递归
		QuickSort(arr, l, right)
	}

}
